"""
01背包问题
"""
# fixme todo
from typing import List


class Solution1:

    def packSolution1(self, w: List[int], v: List[int], volume: int) -> int:
        # dp[i][j]  表示前 i 件物品在 j 容量下获取的最大价值
        n = len(w)
        dp = [[0 for _ in range(0, volume + 1)] for _ in range(0, n + 1)]

        for i in range(0, volume + 1):
            dp[i][0] = 0

        for i in range(1, n + 1):
            for j in range(1, volume + 1):
                if j >= w[i]:
                    # 实际上之和  j  , j- w[i] 有关
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - w[i]] + v[i])

                else:
                    dp[i][j] = dp[i - 1][j]

        return dp[n][volume]
        # dp = [0 for _ in range(0, volume + 1)]
        #
        # for i in range(0, len(w)):
        #     for j in range(0, volume):
        #         dp[j] = max(dp[j], dp[j - w[i]] + v[i])
        #
        # return dp[volume]
